0% completed
Problem Statement
Given a string s containing only a, b, and c characters, return the number of substrings containing at least one occurences of a, b and c characters.
Examples
-
Example 1:
- Input:
"abc" - Expected Output:
1 - Justification: The string itself ("abc") is the only substring containing all three characters.
- Input:
-
Example 2:
- Input:
"abbcca" - Expected Output:
5 - Justification: The substrings containing all 3 characters are "abbc", "abbcc", "abbcca", "bbcca", and "bcca".
- Input:
-
Example 3:
- Input:
"ababacb" - Expected Output:
9 - Justification: The substrings containing all 3 characters are "ababac", "babac", "abac", "bac", "ababacb", "babacb", "abacb", "bacb", and "acb".
- Input:
Solution
To solve this problem, we will use a sliding window approach. This approach is effective as it allows us to dynamically adjust the size of our window (substring) to include all three characters, 'a', 'b', and 'c', while minimizing unnecessary repetitions. The crux of this method is to expand and contract the window based on the presence of 'a', 'b', and 'c' in it. When the window contains all three characters, we'll calculate the number of new substrings this window adds to our total count. This approach is efficient because it requires only one pass through the string, and it's easy to understand and implement.
Step-by-Step Algorithm
-
Initialize Count Array and Pointers:
- Create an array
countwith 3 elements (for 'a', 'b', 'c'), all initialized to 0. - Initialize two pointers:
startat 0 andendat 0. Initializetotalto 0 for counting valid substrings.
- Create an array
-
Iterate with
endPointer:- Incrementally move the
endpointer from the start to the end of the string. - For each character at
end, increase its corresponding count in thecountarray.
- Incrementally move the
-
Check and Adjust
startPointer:- Inside the loop, check if all three characters are present (each count > 0).
- If so, move the
startpointer forward, decrementing the count of the character at thestartposition. Repeat until the window (fromstarttoend) no longer contains all three characters.
-
Update Total Count:
- After adjusting the
startpointer, addstarttototal. This accounts for all valid substrings ending at the currentendcharacter. - Continue until
endhas covered the entire string.
- After adjusting the
-
Return Total Count:
- Return
totalas the number of substrings containing all three characters.
- Return
Algorithm Walkthrough
Let's consider the input: ababacb.
-
Initialize:
count = [0, 0, 0],start = 0,end = 0,total = 0. -
Iteration:
end = 0('a'): Incrementcount[0].count = [1, 0, 0]. No valid substring yet.end = 1('b'): Incrementcount[1].count = [1, 1, 0]. No valid substring yet.end = 2('a'): Incrementcount[0].count = [2, 1, 0]. No valid substring yet.end = 3('b'): Incrementcount[1].count = [2, 2, 0]. No valid substring yet.end = 4('a'): Incrementcount[0].count = [3, 2, 0]. No valid substring yet.end = 5('c'): Incrementcount[2]. Now all characters are present (count = [3, 2, 1]).- Start moving
startwhile the window is valid (all counts > 0):start = 0: Decrementcount[0](character ats[0]is 'a').count = [2, 2, 1].start = 1: Decrementcount[1](character ats[1]is 'b').count = [2, 1, 1].start = 2: Decrementcount[0](character ats[2]is 'a').count = [1, 1, 1].start = 3: Decrementcount[1](character ats[3]is 'b').count = [1, 0, 1].start = 4: Stop as 'b' is no longer in the window.total = total + start = 0 + 4 = 4.
- Start moving
end = 6('b'): Incrementcount[1].count = [1, 1, 1].- Start moving
startagain:start = 4: Decrementcount[0].count = [0, 1, 1].start = 5: Stop as 'a' is no longer in the window.total = total + start = 4 + 5 = 9. Total substrings =9.
- Start moving
-
Final Total:
total = 9.
Code
Complexity Analysis
-
Time Complexity: O(N)
- Each character in the string is visited at most twice (once by the
endpointer and once by thestartpointer). - Despite having nested loops, the total number of operations remains linear with the length of the string.
- Each character in the string is visited at most twice (once by the
-
Space Complexity: O(1)
- The space used does not scale with the size of the input.
- A fixed-size array is used to keep track of the counts of 'a', 'b', and 'c', leading to constant space usage.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis